#include <bits/stdc++.h>
using namespace std;
const int INF = 1000005;
int dp[101][101][10001];
int a[101], n, m;
// [i, j]
int dfs(int i, int j, int k)
{
    // 剪枝
    // 还有剩余素描, 但没有板子了   
    if(j >= i && k == 0) return dp[i][j][k] = INF;
    
    // 还有剩余素描, 但是板子过多
    if(j >= i && k > (j - i + 1)) return dp[i][j][k] = INF;
    
    // 素描覆盖完, 但是还有剩余的板子
    if(i > j && k != 0) return INF;

    // 素描覆盖完, 且没有剩余板子了
    if(i > j && k == 0) return 0;

    // 在 i, j, 且剩余k块儿木板的最优解
    if(dp[i][j][k] != 0) return dp[i][j][k];
    int ans = INF;
    for(int L = i; L <= j; L++)
    {
        int now = INT_MIN;
        for(int t = i; t <= L; ++t)
        {
            now = max(now, a[t]);
        }
        now = now * (L - i + 1);
        ans = min(ans, now + dfs(L + 1, j, k - 1));
    }
    // 记忆化
    return dp[i][j][k] = ans;
}
int main()
{
#ifdef LOCAL
    freopen("ADV-298.in", "r", stdin);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    int ans = dfs(1, n, m);
    cout << ans << endl;
    return 0;
}